from functools import cache
from math import inf
from typing import List


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:

        # 完全背包： 个数可以选多次
        n = len(coins)

        @cache
        # cnt为背包容量
        def dfs(i, cnt):
            # 递归到最后
            if i < 0:
                return 0 if cnt == 0 else inf
            # 如果背包容量 小于 当前 不选
            if cnt < coins[i]:
                return dfs(i - 1, cnt)
            #   取最小 不选 or 选+1  完全背包，选的情况可以反复选，i不需要-1
            return min(dfs(i - 1, cnt), dfs(i, cnt - coins[i]) + 1)

        # 从最后遍历，先选最大的
        res = dfs(n - 1, amount)
        # 如果答案 小于 无穷大 说明有结果可以组成总金额
        return res if res < inf else -1